public class Offer55_1 {
    /**
     * 剑指 Offer 55 - I. 二叉树的深度
     * 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
     *
     * 例如：
     *
     * 给定二叉树 [3,9,20,null,null,15,7]，
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     */
    public static int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left+1,right+1);
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(3);

        TreeNode treeNode2 = new TreeNode(9);
        TreeNode treeNode3 = new TreeNode(20);

        TreeNode treeNode4 = new TreeNode(15);
        TreeNode treeNode5 = new TreeNode(7);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode3.left=treeNode4;
        treeNode3.right = treeNode5;



        treeNode5.right=treeNode2;
        treeNode2.right=treeNode4;
        System.out.println(maxDepth(treeNode1));
    }
}
